package binaryTree;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

//递归函数什么时候需要返回值

//    再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
//    如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
//    如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
//    如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
//

public class PathSum17 {
    //视频中的方法
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
       //递归终止条件
        if(root.left==null&&root.right==null&&targetSum==0){
            return  true;
        }
        if(root.left==null&&root.right==null&&targetSum!=0){
            return  false;
        }
//        左
        if (root.left!=null){
            targetSum-= root.left.val;
            if (hasPathSum(root.left,targetSum)){
                return  true;
            }
            targetSum+= root.left.val;    //回溯了一下  通过下面的方法也知道其实不用回溯也行
        }
        //        右
        if (root.right!=null){
            targetSum-= root.right.val;
            if (hasPathSum(root.right,targetSum)){
                return  true;
            }
            targetSum+= root.right.val;
        }
         return  false;
    }

    public boolean haspathsum1(TreeNode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum1(root.left, targetsum);
            if (left) {      // 已经找到
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum1(root.right, targetsum);
            if (right) {     // 已经找到
                return true;
            }
        }
        return false;
    }

//返回所有可能的路径
//    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
//        List<List<Integer>> resList = new ArrayList<List<Integer>>();
//
//        if (root == null) {
//            return resList;
//        }
//
//
//        targetSum -= root.val;
//        // 叶子结点
//        if (root.left == null && root.right == null) {
//            return targetSum == 0;
//        }
//        if (root.left != null) {
//            boolean left = haspathsum1(root.left, targetSum);
//            if (left) {      // 已经找到
//                return true;
//            }
//        }
//        if (root.right != null) {
//            boolean right = haspathsum1(root.right, targetSum);
//            if (right) {     // 已经找到
//                return true;
//            }
//        }
//        return false;
//
//        return  resList;
//    }
//TODo:  需要再看 自己写不出来
    public List<List<Integer>> pathsum(TreeNode root, int targetsum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; // 非空判断
        List<Integer> path = new LinkedList<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }

    public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new ArrayList<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }
        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }





    public static void main(String[] args) {
        PathSum17 pathSum17 = new PathSum17();
        TreeNode root=new TreeNode(5);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(8);
        TreeNode node3 = new TreeNode(11);
        TreeNode node4 = new TreeNode(13);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(7);
        TreeNode node7 = new TreeNode(2);
        TreeNode node8 = new TreeNode(1);
        root.left=node1;
         root.right=node2;
         node1.left=node3;
         node3.left=node6;
         node3.right=node7;
         node2.left=node4;
         node2.right=node5;
         node5.right=node8;

        System.out.println(pathSum17.hasPathSum(root, 22));


    }
}
